package cxydmmszl.chapter09.t161;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * <li style="color: red;">Prob</li>
 * 路径数组变为统计数组
 * <li style="color: green;">Desc</li>
 * 给定一个路径统计数组 paths，表示一张图。paths[i]==j 代表城市 i 连向城市 j，
 * 如果 paths[i]==i，则表示 i 城市是首都，一张图里只会有一个首都且图中除首都指向自己之外不会有环。
 * <br/>例如，paths=[9,1,4,9,0,4,8,9,0,1]，代表的图如图 9-14 所示。<br/>
 * 由数组表示的图可以知道：<br/>
 * &emsp;&emsp;城市 1 是首都，所以距离为 0，<br/>
 * &emsp;&emsp;离首都距离为 1 的城市只有城市 9，<br/>
 * &emsp;&emsp;离首都距离为 2 的城市有城市 0、3 和 7，<br/>
 * &emsp;&emsp;离首都距离为 3 的城市有城市 4 和 8，<br/>
 * &emsp;&emsp;离首都距离为 4 的城市有城市 2、5 和 6。<br/>
 * 所以，<br/>
 * &emsp;&emsp;距离为 0 的城市有 1 座，<br/>
 * &emsp;&emsp;距离为 1 的城市有 1 座，<br/>
 * &emsp;&emsp;距离为 2 的城市有 3 座，<br/>
 * &emsp;&emsp;距离为 3 的城市有 2 座，<br/>
 * &emsp;&emsp;距离为 4 的城市有 3 座。<br/>
 * 那么统计数组为 nums=[1,1,3,2,3,0,0,0,0,0]。
 * <br/><br/>[要求]<br/>
 * 时间复杂度为 O(n)，额外空间复杂度为 O(1)
 * <br/><br/>备注：<br/>
 * N⩽2∗10^5<br/>
 * 保证输入合法。
 * <li style="color: green;">Input</li>
 * 第一行有一个整数 N，表示节点个数。
 * 接下来一行有 N 个整数表示 paths。
 * <li style="color: green;">Output</li>
 * 输出 N 个整数表示 nums。
 * <li style="color: blue;">Link</li> CD67
 *
 * @author habitplus
 * @since 2021-10-16 16:11
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
            return (int) st.nval;
        } catch (Exception e) {
            throw new RuntimeException("input is invalid!");
        }
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] paths = new int[n];
        for (int i = 0; i < n; i++) {
            paths[i] = nextInt();
        }

        int[] arr = getCountArr(paths);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static int[] getCountArr(int[] paths) {
        if (paths == null || paths.length == 0) return new int[0];
        int n = paths.length;
        int[] res = new int[n];
        // 建立临接表
        HashMap<Integer, ArrayList<Integer>> adj = new HashMap<>();
        int start = -1;
        for (int i = 0; i < n; i++) {
            if (paths[i] == i) {
                start = i;
                continue;
            }
            if (adj.containsKey(paths[i])) {
                adj.get(paths[i]).add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                adj.put(paths[i], list);
            }
        }

        // bfs
        Queue<Integer> que = new LinkedList<>();
        int dis = 0;
        int cur;
        que.add(start);
//        res[0] = 1;

        while (!que.isEmpty()) {

            res[dis++] = que.size();
            for (int i = que.size(); i > 0; i--) {
                cur = que.poll();
                if (adj.containsKey(cur)) {
                    for (int e : adj.get(cur)) {
                        que.add(e);
                    }
                }
            }
        }

        return res;
    }
}
